/**
 * n行m列的棋盘,求机器人从左上走到右下最多有多少条路径
 * 机器人每次只能 往左 或 往下 走一步
 * @param  n n行
 * @param  m m列
 */
// 二维动态规划
var uniquePath = function (n, m) {
    // 初始化一个二维数组,每个点表示到达当前点的路径数
    const memo = []
    for (let i = 0; i < n; i++) {
        memo.push([])
    }
    // 到达第一行和第一列的路径数都为1
    // 第一列置为1
    for (let row = 0; row < n; row++) {
        memo[row][0] = 1
    }
    // 第一行置为1
    for (let col = 0; col < m; col++) {
        memo[0][col] = 1
    }
    for (let row = 1; row < n; row++) {
        for (let col = 1; col < m; col++) {
            // 当前的路径数=上方路径数+左方路径数
            memo[row][col] = memo[row - 1][col] + memo[row][col - 1]
        }
    }
    
    // 返回右下角的终点值
    return memo[n - 1][m - 1]
}